2023-06-25-最小费用最大流

一个重要的定理(Negative Cycle Optimality Conditions)：一个流的费用是最小的(在大小相同的流之中)，当且仅当它对应的残量网络中不存在负环。

正方向是显然的，反方向不好证明，本文暂时略过。

由这个定理，我们可以得到负环消去算法：先找到一个最大流，然后不停地找负环，沿负环增广，直到没有负环为止。

但是更常见的算法是 SSP (Successive Shortest Path) 算法，也就是把EK算法中的bfs换成SPFA。要证明这个算法的正确性，我们需要证明算法过程中不会产生负环。

欲证明：如果一个残量图中没有负环，那么经过一条最短路增广之后不会产生负环

证明：

使用反证法。

假设沿最短路增广后产生了一个负环，由于原先没有负环，必定与的反向路径有一个非空交集。因为是负环，所以，于是，因为增广前后没有变化，所以在增广之前的图中存在，把中替换为，会得到一条新的路径，也可能还会出现与不相连的几个环圈，但是注意到这几个环圈肯定在增广之前就存在(因为增广前后没有变化)，而且增广前没有负环，所以一定比更短，但是这与是最短路矛盾。

Q.E.D